package main

import "fmt"

func main() {
	node := Constructor(2)
	node.Put(1, 1)
	//node.Put(2, 1)
	//node.Put(3, 1)
	//node.Put(4, 1)
	get := node.Get(1)
	fmt.Println(get)
}

type LRUCache struct {
	head *Node
	tail *Node
	hmap map[int]*Node
}
type Node struct {
	key   int
	value int
	next  *Node
	prev  *Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{
		-1, -2, nil, nil,
	}
	tail := &Node{
		-2, -1, nil, nil,
	}
	head.next = tail
	tail.prev = head
	hmap := make(map[int]*Node, 0)
	return LRUCache{
		head, tail, hmap,
	}
}
func insertNode(prev *Node, node *Node) {
	next := prev.next
	node.prev = prev
	node.next = next
	prev.next = node
	next.prev = node
}
func deleteNode(node *Node) {
	next := node.next
	prev := node.prev
	node.next = nil
	node.prev = nil
	next.prev = prev
	prev.next = next
}
func (this *LRUCache) Get(key int) int {
	if v, ok := this.hmap[key]; ok {
		deleteNode(v)
		insertNode((this.head), v)
		return v.value
	}
	return -1
}
func (this *LRUCache) Put(key int, value int) {
	if v, ok := this.hmap[key]; ok {
		v.value = value
		deleteNode(v)
		insertNode((this.head), v)
		return
	}
	node := Node{
		key, value, nil, nil,
	}
	this.hmap[key] = &node
	insertNode((this.head), &node)
}


//
//type LRUCache struct {
//	head     *Node
//	tail     *Node
//	hmap     map[int]*Node
//	capacity int
//}
//type Node struct {
//	key   int
//	value int
//	next  *Node
//	prev  *Node
//}
//
//func Constructor(capacity int) LRUCache {
//	head := &Node{
//		-1, -1, nil, nil,
//	}
//	tail := &Node{
//		-1, -1, nil, nil,
//	}
//	head.next = tail
//	tail.prev = head
//	hmap := make(map[int]*Node, 0)
//	return LRUCache{
//		head, tail, hmap, capacity,
//	}
//}
//func insertNode(prev, node *Node) {
//	next := prev.next
//	node.prev = prev
//	node.next = next
//	prev.next = node
//	next.prev = node
//}
//func deleteNode(node *Node) {
//	next := node.next
//	prev := node.prev
//	node.next = nil
//	node.prev = nil
//	next.prev = prev
//	prev.next = next
//}
//func (this *LRUCache) Get(key int) int {
//	if v, ok := this.hmap[key]; ok {
//		deleteNode(v)
//		insertNode(this.head, v)
//		return v.value
//	}
//	return -1
//}
//func (this *LRUCache) Put(key int, value int) {
//	if v, ok := this.hmap[key]; ok {
//		v.value = value
//		deleteNode(v)
//		insertNode(this.head, v)
//		return
//	}
//	if this.capacity == len(this.hmap) {
//		delete(this.hmap, this.tail.prev.key)
//		deleteNode(this.tail.prev)
//	}
//	node := &Node{
//		key, value, nil, nil,
//	}
//	this.hmap[key] =node
//	insertNode(this.head, node)
//}